package com.jia.leetCode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/problems/brick-wall/submissions/
 * @author: STU756
 * @create: 2020-08-22 14:21
 */
public class Pro0554 {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer,Integer> map = new HashMap<>();
        int max = 0;
        for(List<Integer> w : wall) {
            int preSum = 0;
            if(w.size() > 1) {
                for(int i = 0; i < w.size()-1;i++) {
                    preSum += w.get(i);
                    map.put(preSum, map.getOrDefault(preSum, 0) + 1);
                    max = Math.max(max, map.get(preSum));
                }
            }
        }
        return wall.size() - max;
    }
}
